1
敵対的探索と制約充足
PolyU COMP5511Lecture 3
00:05

人工知能の概念 (PolyU COMP5511) の第3課へようこそ。 人工知能の概念 (PolyU COMP5511)。このセッションでは、単一エージェントの経路探索から、 敵対的探索、エージェントが競争的なマルチエージェント環境で動作するようになります。また、 制約充足問題（CSP）、経路ではなく特定の制約を満たす状態を見つけることを目標とするパラダイムを導入します。

コアコンセプト

  • 敵対的探索： インテリジェントな対戦相手に対して合理的な意思決定を行うための、 ミニマックス および アルファベータ枝刈り のようなアルゴリズムに焦点を当てます。
  • モンテカルロ木探索（MCTS）： 確定的ではない意思決定を探求し、 AlphaGoのような最新のゲームAIの基盤となっています。
  • 制約充足： 変数、ドメイン、制約を使用して問題をモデル化し、 バックトラッキング および ローカルサーチのような最新のゲームAIの基盤となっています。

複雑性解析

敵対的な状況では、探索空間の複雑さは、ゲームの分岐係数 b と深さ dによって定義されることが多く、計算コストは次のようになります。 O（bd） この指数関数的な増加により、アルファベータ枝刈りのような効率的な枝刈り戦略が必要となります。

パラダイムシフトに関する注意
環境が静的な標準的な探索（例：A* または BFS）とは異なり、 敵対的探索 は、環境（対戦相手）が積極的にあなたの成功を最小限に抑えようとすると仮定します。CSP では、 CSP、アクションの順序は最終的な割り当ての妥当性よりも重要ではありません。
概念的擬似コード：エージェントのタイプ
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).
Gallery Image